%!TEX program = xelatex
\documentclass[lang=cn,10pt]{elegantbook}

% 本文档命令
\usepackage{array,url}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}
\newcommand{\code}[1]{\lstinline{#1}}


% 文档区
\begin{document}

\chapter*{数值分析作业--Week1}

\begin{problem}
考虑二分法初始区间$[1.5,3.5]$，则第$n$步中搜索区间宽度是？根$r$与迭代搜索区间中点的上确界是？
\end{problem}
\begin{proof} \par
i)  $|3.5-1.5|^{2-n} = 2^{2-n}$ \par
ii) 求解$\sup|r-c_n|$\par
    当$r\in [1.5,2]\cup[3,3.5]$时，$|r-2.5|\geq 0.5$，对于$n\geq 2$有
    \[|r-c_n|\leq 2^{n-1}\leq 0.5\]
    当$r\in [2.25,2.75]$时，$|r-2.5|\leq 0.25 $ ,同时$c_2\in\{2,3\}\implies |r-c_2|\geq 0.75$，对于$n\geq 3$有
    \[|r-c_3|\leq 2^{n-1}\leq 0.25\]
    对于$r\in[2,2.25]\cup[2.75,3]$，有$|r-2.5|\geq 0.25$，对于$n\geq 2$有
    \[|r-c_n|\leq 0.25\]
    故综上
    \[
    \sup|r-c_n| = 
    \begin{cases}
    |r-2.5|\qquad r\leq 2.25 \wedge r\geq 2.75 \\
    min\{|r-2|,|r-3|\} 2.25\leq r\leq 2.75 
    \end{cases}
    \]
\end{proof}

\begin{problem}
二分法初始区间$[a_0,b_0]$有$a_0>0$，目的是求出相对误差不大于$\varepsilon$的解，证明若有下式则必然达到目标：
\[n\geq \dfrac{\log{(b_0-a_0)}-\log{\varepsilon}-\log{a_0}}{\log{2}}-1\]
\end{problem}
\begin{proof}
容易知道$|r-c_n|\leq \dfrac{b_0-a_0)}{2^{n+1}}$，故容易看出
\[\dfrac{b_0-a_0}{|a_0|2^n}\leq \varepsilon\]
即
\[n\geq \log_2(b_0-a_0)-\log_2 \varepsilon - \log_2a_0-1\]
\end{proof}

\begin{problem}
通过手算对$4x^3-2x^2+3=0$以起始点$x_0=-1$进行4次牛顿迭代，迭代解用表展示出来。
\end{problem}
\begin{proof}
$p'(x)=12x^2-4x$ 
则可以有下面的迭代格式
\[x_{n+1}=x_n-\frac{4x_n^3-2x_n^2+3}{12x_n^2-4x_n}\]
通过简单的整数计算，不难得到如下结果
\begin{center}
\begin{tabular}{c|c}
    n & $x_n$ \\ \hline
    0 & -1 \\ \hline
    1 & $-\tfrac{13}{16}$ \\ \hline
    2 & $-\tfrac{46015}{50752}$ \\ \hline
    3 & $-\tfrac{157514349365309}{1852131320715520}$ \\ \hline
    4 & $-\tfrac{73359138781169712745501824028317449227422367087}{83221405643646822219799229152360668535823303680}$
\end{tabular}
\end{center}
\end{proof}

\begin{problem}
考虑另一种牛顿迭代，迭代格式：
\[x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_0)}\]
确定$s$与$C$使得$e_{n+1} = C e_n^s$，$C$可依赖于$x_n,f,f'$与根$r$。
\end{problem}
\begin{proof}
\[e_{n+1} = e_n|1-\dfrac{f_{[x_n,r]}}{f'(x_0)}|\]
其中
\[C = |1-\dfrac{f_{[x_n,r]}}{f'(x_0)}| \qquad s = 1\]
\end{proof}

\begin{problem}
在$(-\tfrac{\pi}{2},\tfrac{\pi}{2})$中，迭代$x_{n+1} = \tan^{-1}x_n$是否收敛？
\end{problem}
\begin{proof}
不失一般性设$x_0\geq 0$，由Lagrange中值定理有
\[\dfrac{\arctan x_n}{x_n} = \dfrac{1}{1+\xi_n^2} \leq 1\]
从而
\[x_{n+1}\leq x_n\]
由单调有界定理
\[x_n \searrow \alpha \]
且$\arctan \alpha = \alpha \implies \alpha = 0 $，故收敛且极限为0。
\end{proof}

\begin{problem}
$p>1$，求以下连分数
\[x = \dfrac{1}{p+\dfrac{1}{p+\dfrac{1}{p+\cdot}}}\]
证明生成它的数列收敛。
\end{problem}
\begin{proof}
容易说明迭代格式
\[x_{n+1}= \dfrac{1}{p+x_n} \]
则
\[\begin{cases}
x_{n+2} = \dfrac{1}{p+\dfrac{1}{p+x_n}} \\
x_{n+3} = \dfrac{1}{p+\dfrac{1}{p+\dfrac{1}{x_n}}}
\end{cases}\]
从而
\[\begin{cases}
x_{n+2}\geq x_{n} \Leftrightarrow x_{n+1}\geq x_{n+3} \\
x_{n+2}\leq x_{n} \Leftrightarrow x_{n+1}\leq x_{n+3}
\end{cases}\]
注意到$x_1\geq x_3, x_2\leq x_4$，故
\[\begin{cases}
x_1\geq x_3 \geq x_5\geq \cdots \\
x_2\leq x_4 \leq x_6\leq \cdots \\
\end{cases}\]
类似容易说明$x_{2k}\leq x_1, x_{2k+1}\geq x_2$
\end{proof}
由单调有界定理，有$\lim\limits_{n\to\infty}x_{2n+1} = \alpha, \lim\limits_{n\to\infty}x_{2n} = \beta $并且
\[a = \dfrac{1}{p+\dfrac{1}{p+a}}\quad b = \dfrac{1}{p+\dfrac{1}{p+b}}\] 
做差通分得
\[(a-b)(p^2+p(a+b)+p-1)=0 \]
从而$a=b$，即证$\lim\limits_{n\to\infty}x_{n} = \alpha = \beta = x$，$x$存在，又$x$是前文迭代格式的大于0的不动点，则
\[x = \sqrt{\tfrac{p^2}{4}+1}-\tfrac{p}{2}\]
\begin{problem}
问题0.2中的$a_0,b_0$若$a_0<0<b_0$，尝试给出一个类似的估计。在这里还使用相对误差是否合适？
\end{problem}
\begin{proof}
我们类似讨论绝对误差，有以下容易说明的结论
\[n\geq \log_2(b_0-a_0) - \log_2 \varepsilon -1\]
是绝对误差小于等于$\varepsilon$的充分条件，以下例子说明相对误差不是好的评估，考虑
\[f(x)=(x+\frac{1}{n})(x-1),\quad a_0 = -\frac{1}{2},b_0 = \frac{1}{2}\]
有相对误差
\[|1-\frac{n}{2^k}|\]在第$k$步极大，若$k<<\log_2 n$
\end{proof}

\end{document}
